#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;


//  Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0||inorder.size()==0){
            return NULL;
        }
        int i = 0;
        set<int> S;        
        TreeNode* head = func(preorder,inorder,i,S);
        return head;

    }
    TreeNode* func(vector<int>& preorder, vector<int>& inorder, int& i, set<int>& S){
        if(inorder.size()==0||i==preorder.size()||S.find(preorder[i])!=S.end()){
            return NULL;
        }
        TreeNode* head = new TreeNode(preorder[i]);
        S.insert(preorder[i]);
        auto index = find(inorder.begin(),inorder.end(),preorder[i]);
        vector<int> leftorder(inorder.begin(),index);
        vector<int> rightorder(index+1,inorder.end());
        i = i+1;
        head->left = func(preorder,leftorder,i,S);
        head->right = func(preorder,rightorder,i,S);
        return head;
    }
};
